package com.huawei.M01.iterator;

import java.util.ArrayList;
import java.util.List;

/**
 * 中序遍历
 *
 * @author li
 */
public class InOrderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        afterOrder(root, result);
        return result;
    }

    /**
     * 二叉树中序遍历
     *
     * @param root   根节点
     * @param result 最终结果
     */
    private void inOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inOrder(root.left, result);
        result.add(root.val);
        inOrder(root.right, result);
    }

    /**
     * 前序遍历
     * @param root 根节点
     * @param result 遍历之后的结果
     */
    private void beforeOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        beforeOrder(root.left, result);
        beforeOrder(root.right, result);
    }

    private void afterOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        afterOrder(root.left, result);
        afterOrder(root.right, result);
        result.add(root.val);
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
